1. Field of the Invention
The present invention relates to a method of processing a program by parallel processing, using a plurality of processors. It also relates to a processing unit for carrying out such a process.
2. Summary of the Prior Art
In order to process a program by parallel processing, the program is divided into a plurality of partial programs, which are then distributed among a plurality of processors of a processing unit for processing. Each processor processes one or more of the partial programs. The speed of the processing of the program is then determined by the speed of processing of the partial programs assigned to each processor, with the processor which takes longest to process its assigned partial programs being the one which has the maximum influence on the overall processing time. Thus, if the parallel processing unit is to operate efficiently, it is important that the partial programs are distributed so that each processor will take approximately the same time as all other processors to process the partial programs assigned to it. It is therefore necessary to determine an efficient distribution of the partial programs, a process which is known as "load diffusion".
There are two types of load diffusion, namely static load diffusion and dynamic load diffusion. In static load diffusion, the assignment of the partial programs to the processors is predetermined prior to the processing of those partial programs by the processors. In dynamic load diffusion, the distribution of the partial programs is changed whilst the processors are processing the partial programs.
JP-A-3-41523 proposed a method of static load diffusion, in which a multi-step network switch was provided. This switch was a hardware component which was configured in advance of processing, to assign the partial programs to the processors.
JP-A-2-280266 was concerned with dynamic load diffusion in which each processor determined whether it had a high level of processing to be carried out. When that high level was detected, it generated a signal requesting that processing of partial programs be transferred to other processing units.
In JP-A-3-103964, a processor which had completed the processing of the partial programs assigned to it was arranged to receive partial programs from an adjacent processor which had not completed the processing of its assigned partial programs. Thus, JP-A-3-103964 was also concerned with dynamic load diffusion.
Similar monitoring of adjacent processors occurred in JP-A-63-76017.
Finally, JP-A-2-178755 proposed that thresholds effect for each processor, being an upper threshold and a lower threshold. Then, if the amount of the processing needed by one processor exceeded the upper threshold, then further assignment of partial programs to that processor was halted. Similarly, if the amount of processing for a processor was less than the lower threshold, that processor was ready to receive further partial programs.